/**
 * @file     fourSum.js
 * @brief    [18. 四数之和](https://leetcode-cn.com/problems/4sum/)
 * @author   Zhu
 * @date     2022-03-15 22:29
 */

/**
 * 排序 + 递归 + 剪枝
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
    nums.sort((a, b) => a - b);

    function twoSum(nums, target) {
        const result = [];
        let left = 0;
        let right = nums.length - 1;
        while (left < right) {
            if (nums[left] + nums[right] === target) {
                result.push([nums[left], nums[right]]);
                do {
                    left++;
                } while (nums[left] === nums[left - 1]);
                do {
                    right--;
                } while (nums[right] === nums[right + 1]);
            } else if (nums[left] + nums[right] > target) right--;
            else left++;
        }
        return result;
    }

    function nSum(nums, target, n) {
        // 剪枝
        if (nums.slice(0, n).reduce((a, c) => a + c, 0) > target) return [];
        if (nums.slice(-n).reduce((a, c) => a + c, 0) < target) return [];
        // 递归
        if (n === 2) return twoSum(nums, target);
        const result = [];
        for (let k = 0; k < nums.length; k++) {
            const min = nums[k];
            const res = nSum(nums.slice(k + 1), target - min, n - 1);
            if (res.length) result.push(...res.map((r) => [min, ...r]));
            while (nums[k + 1] === min) k++;
        }
        return result;
    }

    return nSum(nums, target, 4);
};
